{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Contains Duplicate II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: containsNearbyDuplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #存在重复元素 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code> 和一个整数&nbsp;<code>k</code> ，判断数组中是否存在两个 <strong>不同的索引</strong><em>&nbsp;</em><code>i</code>&nbsp;和<em>&nbsp;</em><code>j</code> ，满足 <code>nums[i] == nums[j]</code> 且 <code>abs(i - j) &lt;= k</code> 。如果存在，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,1], k<em> </em>= 3\n",
    "<strong>输出：</strong>true</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,0,1,1], k<em> </em>=<em> </em>1\n",
    "<strong>输出：</strong>true</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,1,2,3], k<em> </em>=<em> </em>2\n",
    "<strong>输出：</strong>false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [contains-duplicate-ii](https://leetcode.cn/problems/contains-duplicate-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [contains-duplicate-ii](https://leetcode.cn/problems/contains-duplicate-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]\\n3', '[1,0,1,1]\\n1', '[1,2,3,1,2,3]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        \n",
    "        dic = {}\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "        \tif nums[i] in dic:\n",
    "        \t\treturn True\n",
    "        \telse:\n",
    "        \t\tdic[nums[i]] = True\n",
    "\n",
    "        \tif len(dic) == k + 1:\n",
    "        \t\tdel dic[nums[i - k]]\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: 'List[int]', k: 'int') -> 'bool':\n",
    "        if k < 0:\n",
    "            return False\n",
    "        li = list()\n",
    "        size = 0\n",
    "        for i in nums:\n",
    "            if i in li:\n",
    "                return True\n",
    "            li.append(i)\n",
    "            if len(li) > k:\n",
    "                li.pop(0)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        s = set()\n",
    "        for i in range(len(nums)):\n",
    "            if len(s) == k + 1:\n",
    "                s.remove(nums[i - k - 1])\n",
    "            if nums[i] in s:\n",
    "                return True\n",
    "            s.add(nums[i])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        s = set()\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > k:\n",
    "                s.remove(nums[i - k - 1])\n",
    "            if x not in s:\n",
    "                s.add(x)\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        nums_sorted_index=sorted(range(len(nums)),key=lambda x:nums[x])\n",
    "        print(nums_sorted_index)\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums_sorted_index[i+1]<=nums_sorted_index[i]+k and nums[nums_sorted_index[i+1]]==nums[nums_sorted_index[i]]:\n",
    "                return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        counter = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if i > k:\n",
    "                counter[nums[i - k - 1]] = 0\n",
    "            if counter.get(num, 0) > 0:\n",
    "                return True\n",
    "            counter[num] = 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: 'List[int]', k: 'int') -> 'bool':\n",
    "        if len(nums) < 2: return False\n",
    "        if len(nums) <= k:\n",
    "            if len(set(nums)) < len(nums):\n",
    "                return True\n",
    "        for i in range(len(nums)-k): #只能取到len(nums)-k-1 \n",
    "            win = nums[i:i+k+1] #contain k+1个元素\n",
    "            if len(set(win)) == k+1:\n",
    "                continue\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        array=[]\n",
    "        for num in nums:\n",
    "            if num in array:\n",
    "                if len(array)-array.index(num)<=k:\n",
    "                    return True\n",
    "                else:\n",
    "                    array[array.index(num)]=None\n",
    "            array.append(num)\n",
    "        return False    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        start = nums[0:k+1]\n",
    "        temp = nums[0:k+1]\n",
    "        temp.sort()\n",
    "        for j in range(0,len(temp)-1):\n",
    "            if temp[j] == temp[j+1]:\n",
    "                return True\n",
    "        for i in nums[k+1:]:\n",
    "            del start[0]\n",
    "            #print(start)\n",
    "            if i in start:\n",
    "                return True\n",
    "            start.append(i)        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            if num in stack:\n",
    "                return True\n",
    "            stack.append(num)\n",
    "            if len(stack) > k:\n",
    "                del stack[0]\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        windows = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in windows:\n",
    "                return True\n",
    "            windows.append(nums[i])\n",
    "            if len(windows) > k:\n",
    "                windows.pop(0)\n",
    "        return False\n",
    "\n",
    "'''\n",
    "为什么不用数组，而是用集合\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) == 0:\n",
    "            return False\n",
    "\n",
    "        duplicate_set = set()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in duplicate_set:\n",
    "                return True\n",
    "            else:\n",
    "                duplicate_set.add(nums[i])\n",
    "            \n",
    "            if len(duplicate_set) > k:\n",
    "                duplicate_set.remove(nums[i-k])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        ans=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in ans:\n",
    "                return True\n",
    "            else:\n",
    "                ans.append(nums[i])\n",
    "            if len(ans)>k:\n",
    "                del ans[0]\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        ans = []\n",
    "        for n in nums:\n",
    "            if n in ans:\n",
    "                return True\n",
    "            else:\n",
    "                ans.append(n)\n",
    "                if len(ans) > k:\n",
    "                    ans.pop(0)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def insertion_sort(self, A, B, k):\n",
    "        for j in range(1, len(A), 1):\n",
    "            key = A[j]\n",
    "            i = j - 1\n",
    "            while i >= 0 and A[i] > key:\n",
    "                A[i + 1] = A[i]\n",
    "                B[i + 1] = B[i]\n",
    "                i = i - 1\n",
    "            A[i + 1] = key\n",
    "            B[i + 1] = j\n",
    "        \n",
    "        for i in range(len(A) - 1):\n",
    "            if A[i] == A[i + 1] and math.fabs(B[i] - B[i + 1]) <= k:\n",
    "                return True\n",
    "        return False\n",
    "    \n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) <= 1:\n",
    "            return False;\n",
    "        B = []\n",
    "        for i in range(len(nums)):\n",
    "            B.append(i)\n",
    "        return self.insertion_sort(nums, B, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        nearbySet = set()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in nearbySet:\n",
    "                return True\n",
    "            else:\n",
    "                nearbySet.add(nums[i])\n",
    "                if i >= k:\n",
    "                    nearbySet.remove(nums[i - k])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        set1=set()\n",
    "        if k==0 or len(nums)<2:\n",
    "            return False\n",
    "        for i in range(min(k+1,len(nums))):\n",
    "            set1.add(nums[i])\n",
    "        if len(set1)<min(k+1,len(nums)):\n",
    "            return True\n",
    "        else:\n",
    "            for i in range(k+1,len(nums)):\n",
    "                set1.remove(nums[i-k-1])\n",
    "                set1.add(nums[i])\n",
    "                if len(set1)<k+1:\n",
    "                    return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        if k==0:\n",
    "            return False\n",
    "        if k>len(nums):\n",
    "            hashT = set(nums)\n",
    "            if len(hashT)<len(nums):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        hashT = set(nums[0:k])\n",
    "        if len(hashT)<k:\n",
    "            return True\n",
    "        for i in range(k,len(nums)):\n",
    "            if nums[i] in hashT:\n",
    "                return True\n",
    "            else:\n",
    "                hashT.remove(nums[i-k])\n",
    "                hashT.add(nums[i])\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        nums_dict = {}\n",
    "\n",
    "        for i,n in enumerate(nums):\n",
    "            if n in nums_dict:\n",
    "                return True\n",
    "            nums_dict[n] = i\n",
    "            if len(nums_dict) > k:\n",
    "                del nums_dict[nums[i-k]]\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        dict_c = {}\n",
    "        for i in range(len(nums)):\n",
    "            if i >k:\n",
    "                dict_c[nums[i-k-1]] -= 1\n",
    "                if dict_c[nums[i-k-1]] ==0:\n",
    "                    dict_c.pop(nums[i-k-1])\n",
    "            if nums[i] in dict_c:\n",
    "                return True\n",
    "            dict_c[nums[i]] = dict_c.get(nums[i],0)+1\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        dic = {}\n",
    "        for i in range(min(k, len(nums))):\n",
    "            if dic.get(nums[i], 0) > 0:\n",
    "                return True\n",
    "            dic[nums[i]] = 1\n",
    "        j = k\n",
    "        while(j < len(nums)):\n",
    "            if dic.get(nums[j], 0) > 0:\n",
    "                return True\n",
    "            dic[nums[j]] = 1\n",
    "            i = j-k\n",
    "            dic[nums[i]] -= 1\n",
    "            j += 1\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        \n",
    "        if(len(nums) == 0 or k ==0 ):\n",
    "            return False\n",
    "\n",
    "        minlen= min(len(nums),k+1)\n",
    "        if len(set(nums[:minlen]))< minlen:\n",
    "            return True\n",
    "        dict_keys = dict.fromkeys(nums[:k], 1)\n",
    "        #print(dict_keys)\n",
    "        for i in range(k,len(nums)):\n",
    "            if dict_keys.get(nums[i],0) == 0:\n",
    "                del dict_keys[nums[i-k]]\n",
    "                dict_keys[nums[i]] = 1\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        if len(set(nums[0:k + 1])) < len(nums[0:k + 1]):\n",
    "            return True\n",
    "        l = len(nums) - 1\n",
    "        i = k + 1\n",
    "        while i <= l:\n",
    "            if nums[i] in nums[i - k:i]:\n",
    "                return True\n",
    "            i += 1\n",
    "        return False\n",
    "        # hash={}\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] not in hash:\n",
    "        #         hash[nums[i]]=i\n",
    "        #     else:\n",
    "        #         if i-hash[nums[i]]<=k:\n",
    "        #             return True\n",
    "        #         else:\n",
    "        #             hash[nums[i]]=i\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            if i > k:\n",
    "                s.remove(nums[i-k-1])\n",
    "            if nums[i] in s:\n",
    "                return True\n",
    "            s.add(nums[i])\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        window = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if len(window) == k + 1:\n",
    "                window.remove(window[0])\n",
    "            if num in window:\n",
    "                return True\n",
    "            window.append(num)\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        # d={}\n",
    "        # for i,v in enumerate(nums):\n",
    "        #     if v in d and i-d[v]<=k:\n",
    "        #         return True\n",
    "        #     d[v]=i\n",
    "        # return False\n",
    "        L=[]\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if len(L) >k:\n",
    "                L.pop(0)\n",
    "            if nums[i] in L:\n",
    "                return True\n",
    "            L.append(nums[i])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        ids = []\n",
    "        p = 0\n",
    "        for i in range(len(nums)):\n",
    "            if(i-p>k):\n",
    "                ids.pop(0)\n",
    "                p = p + 1\n",
    "\n",
    " \n",
    "            if(nums[i] in ids):\n",
    "                return True\n",
    "\n",
    "            ids.append(nums[i])\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] in nums[i+1:i+k+1]:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            if i > k:\n",
    "                s.remove(nums[i - k - 1])\n",
    "            if nums[i] in s:\n",
    "                return True\n",
    "            s.add(nums[i])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        check = set()\n",
    "        n = len(nums)\n",
    "        for idx, obj in enumerate(nums):\n",
    "            if idx > k:\n",
    "                check.remove(nums[idx-k-1])\n",
    "            if obj in check:\n",
    "                return True\n",
    "            check.add(obj)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "   \n",
    "\n",
    "        sorted_indices = sorted(range(len(nums)), key=lambda i: nums[i])\n",
    "        nums = [nums[i] for i in sorted_indices]\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            if (nums[i]==nums[i-1]):\n",
    "                if(abs(sorted_indices[i]-sorted_indices[i-1]<=k)):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        l=len(nums)\n",
    "        nums_=[]\n",
    "        for i in range(l):\n",
    "            \n",
    "            nums_.append(nums[i]*10**6+i)     \n",
    "        nums_=sorted(nums_)\n",
    "        for i in range(l-1):\n",
    "            if nums_[i]//10**6==nums_[i+1]//10**6:\n",
    "                if -(nums_[i]-nums_[i+1])<=k:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        index = [idx for idx in range(n)]\n",
    "        index.sort(key=lambda x: nums[x])\n",
    "        nums = [nums[i] for i in index]\n",
    "        for i in range(1, n):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                if abs(index[i]-index[i-1])<=k:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        index = [idx for idx in range(n)]\n",
    "        index.sort(key=lambda x: nums[x])\n",
    "        nums = [nums[i] for i in index]\n",
    "        for i in range(1, n):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                if abs(index[i]-index[i-1])<=k:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        left=0\n",
    "        cnt=Counter()\n",
    "\n",
    "        for right in range(len(nums)):\n",
    "            \n",
    "            if cnt[nums[right]]!=0:\n",
    "                return True\n",
    "\n",
    "            cnt[nums[right]]+=1\n",
    "            \n",
    "            if right-left+1>k:\n",
    "                cnt[nums[left]]-=1\n",
    "                left+=1\n",
    "                \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        pos = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in pos and i - pos[num] <= k:\n",
    "                return True\n",
    "            pos[num] = i\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        result=False\n",
    "        hash={}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in hash.keys():\n",
    "                n=hash[nums[i]]\n",
    "                l=i-n\n",
    "                print(l)\n",
    "                if abs(l)<=k:\n",
    "                    result=True\n",
    "                    print(nums[i],i)\n",
    "                    break\n",
    "               \n",
    "            hash[nums[i]]=i\n",
    "                \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        counter = collections.defaultdict(int)\n",
    "        l, r = 0, 0\n",
    "        while r < len(nums):\n",
    "            counter[nums[r]] += 1\n",
    "            if counter[nums[r]] > 1:\n",
    "                return True\n",
    "            if r-l == k:\n",
    "                counter[nums[l]] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        hashtab = {}\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] in hashtab:\n",
    "                if i-hashtab[nums[i]]<=k: return True\n",
    "                else: hashtab[nums[i]]=i\n",
    "            else:\n",
    "                hashtab[nums[i]] = i\n",
    "        return False\n",
    "\n",
    "        # hashtab = {}\n",
    "        # for i, num in enumerate(nums):\n",
    "        #     if num in hashtab:\n",
    "        #         if i-hashtab[num]<=k: return True\n",
    "        #         else:\n",
    "        #             hashtab[num]=i # 如果间隔大于k，则更新当前idx\n",
    "        #     else:\n",
    "        #         hashtab[num] = i\n",
    "        # return False\n",
    "\n",
    "        ## 思路：用哈希表存储当前值的idx，每次从tab中查找\n",
    "        \n",
    "        # dic = {}\n",
    "        # for j,val in enumerate(nums):\n",
    "        #     if val not in dic:\n",
    "        #         dic[val] = j\n",
    "        #     else:\n",
    "        #         i = dic[val]\n",
    "        #         if j-i<=k: return True\n",
    "        #         else: dic[val] = j\n",
    "                \n",
    "        # return False\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        d = dict()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in d:\n",
    "                print(i, num)\n",
    "                d[num] = i\n",
    "            else:\n",
    "                if i - d[num] <= k:\n",
    "                    print(i - d[num])\n",
    "                    return True\n",
    "                else:\n",
    "                    d[num] = i\n",
    "        print(d)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums)==len(set(nums)):\n",
    "            return False\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]==nums[j] and abs(i-j)<=k:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        # res = False\n",
    "        # if len(nums) == len(set(nums)):\n",
    "        #     return res\n",
    "        # for i in range(len(nums)):\n",
    "        #     test_list = nums[i:i+k+1]\n",
    "        #     if len(test_list) != len(set(test_list)):\n",
    "        #         res = True\n",
    "        # return res\n",
    "\n",
    "        # left = 0 \n",
    "        # ans = False\n",
    "        # s = set()\n",
    "        # for right, x in enumerate(nums):\n",
    "        #     if right - left > k:\n",
    "        #         s.remove(nums[left])\n",
    "        #         left +=1\n",
    "        #     if x in s:\n",
    "        #         return True\n",
    "        #     s.add(x)\n",
    "        # return False\n",
    "\n",
    "        # if len(nums) == len(set(nums)):\n",
    "        #     return False\n",
    "        # for i in range(len(nums) - 1):\n",
    "        #     for j in range(i+1, len(nums)):\n",
    "        #         if nums[i] == nums[j] and abs(i - j) <= k:\n",
    "        #             return True\n",
    "        # return False\n",
    "\n",
    "        if len(nums) == len(set(nums)):    # 如果原list中没有重复元素\n",
    "            return False\n",
    "        for index, left in enumerate(nums[:]):\n",
    "            for right in nums[index+1:index+k+1]:\n",
    "                if right == left:\n",
    "                    return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        if len(set(nums)) == len(nums):\n",
    "            return False\n",
    "\n",
    "        for i in range(len(nums) - 1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] == nums[j] and abs(i - j) <= k:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        if len(set(nums)) == len(nums):\n",
    "            return False\n",
    "        dic = defaultdict(list)\n",
    "        n = 0\n",
    "        while n <= len(nums)-1:\n",
    "            dic[nums[n]].append(n)\n",
    "            n += 1\n",
    "        print(dic.values())\n",
    "        for i in dic.values():\n",
    "            if len(i)>1:\n",
    "                x = len(i)-1\n",
    "                while x > 0:\n",
    "                    temp = i[x] - i[x-1]\n",
    "                    if abs(temp) <= k:\n",
    "                        return True\n",
    "                    x -= 1\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if k == 0 or n < 2: return False\n",
    "        \n",
    "        m2 = defaultdict(set)\n",
    "\n",
    "        for i in range(min(k+1, n)):\n",
    "            if nums[i] not in m2:\n",
    "                m2[nums[i]] = set()\n",
    "            m2[nums[i]].add(i)\n",
    "        \n",
    "        if len(m2) != min(k+1, n):\n",
    "            return True\n",
    "        \n",
    "        for i in range(k+1, n):\n",
    "            index_to_del = i - k - 1\n",
    "            num_to_del = nums[index_to_del]\n",
    "            m2[num_to_del].remove(index_to_del)\n",
    "            if len(m2[num_to_del]) == 0:\n",
    "                m2.pop(num_to_del)\n",
    "            if nums[i] in m2:\n",
    "                return True\n",
    "            m2[nums[i]].add(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        nums2 = []\n",
    "        for i in range(n):\n",
    "            nums2.append([nums[i],i])\n",
    "        nums2.sort()\n",
    "        for i in range(n-1):\n",
    "            if nums2[i][0] == nums2[i+1][0] and abs(nums2[i][1] - nums2[i+1][1]) <= k:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        repidic={}\n",
    "        indeic={}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in repidic:\n",
    "                repidic[nums[i]]=10E5\n",
    "                indeic[nums[i]]=i\n",
    "            else:\n",
    "                repidic[nums[i]]=min(repidic[nums[i]],i-indeic[nums[i]])\n",
    "                if repidic[nums[i]]<=k:\n",
    "                    return True\n",
    "                indeic[nums[i]]=i\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        r = []\n",
    "        for i in range(len(nums)):\n",
    "            r.append((i,nums[i]))\n",
    "        r = sorted(r,key=lambda x:x[-1])\n",
    "\n",
    "        for i in range(len(r)-1):\n",
    "            cur_idx,cur_val = r[i]\n",
    "            next_idx,next_val = r[i+1]\n",
    "            if cur_val == next_val and abs(cur_idx-next_idx) <=k:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        if k==0:\n",
    "            return False\n",
    "        if len(nums)==1:\n",
    "            return False\n",
    "        if k>=len(nums):\n",
    "            l=nums.sort()\n",
    "            i=0\n",
    "            while i<len(nums)-1:\n",
    "                if nums[i]==nums[i+1]:\n",
    "                    return True\n",
    "                i+=1\n",
    "            return False\n",
    "        i=0\n",
    "        dic={}\n",
    "        while i<len(nums):\n",
    "            '''last=min(i+k,len(nums)-1)\n",
    "            for j in range(i,last+1):\n",
    "                if str(nums[j]) in dic:\n",
    "                    if abs(dic[str(nums[j])]-j)'''\n",
    "            string=str(nums[i])\n",
    "            if string in dic:\n",
    "                if abs(dic[string]-i)<=k:\n",
    "                    return True\n",
    "                else:\n",
    "                    dic[string]=i\n",
    "            else:\n",
    "                dic[string]=i\n",
    "            i+=1\n",
    "        return False\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        flag = False\n",
    "        a = {}\n",
    "        b = {}\n",
    "        res = inf\n",
    "        for i, v in enumerate(nums):\n",
    "            a[i] = v\n",
    "        for kk, v in a.items():\n",
    "            if v not in b:\n",
    "                b[v]=kk\n",
    "            else:\n",
    "                if abs(kk-b[v])>k:#(这里还需要考虑【1 0 1 1】这种情况)\n",
    "                    b[v] = kk\n",
    "                else:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        compare_list=[]\n",
    "        for i in range(len(nums)):\n",
    "            compare_list.append([nums[i],i])\n",
    "        compare_list=sorted(compare_list,key=lambda x:x[0])\n",
    "        for j in range(len(nums)-1):\n",
    "            if compare_list[j][0]==compare_list[j+1][0]:\n",
    "                if max(compare_list[j][1],compare_list[j+1][1])-min(compare_list[j][1],compare_list[j+1][1])<=k:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        duplicate_count = {}\n",
    "        for index, val in enumerate(nums):\n",
    "            if val not in duplicate_count:\n",
    "                duplicate_count[val] = [index]\n",
    "            else:\n",
    "                duplicate_count[val].append(index)\n",
    "        for key, vals in duplicate_count.items():\n",
    "            if len(vals) <= 1:\n",
    "                continue\n",
    "            slow = 0\n",
    "            fast = 1\n",
    "            while fast < len(vals) and vals[fast] - vals[slow] > k:\n",
    "                slow = fast\n",
    "                fast += 1\n",
    "\n",
    "            if fast < len(vals) and vals[fast] - vals[slow] <= k:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        n=len(nums)\n",
    "        dic=dict()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in dic:\n",
    "                dic[nums[i]].append(i)\n",
    "            else:\n",
    "                dic[nums[i]]=[i]\n",
    "        for o,v in dic.items():\n",
    "            print(v)\n",
    "            for j in range(1,len(v)):\n",
    "                if abs(v[j]-v[j-1])<=k:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:\n",
    "        dic = {}\n",
    "        for k1,v in enumerate(nums):\n",
    "            dic[v] = dic.get(v,[])+[k1]\n",
    "        print(dic)\n",
    "        for num in dic:\n",
    "            # index_list = sorted(dic[num])\n",
    "            index_list = dic[num]\n",
    "            for i in range(len(index_list)-1):\n",
    "                if (index_list[i+1]-index_list[i]) <= k:\n",
    "                    print(index_list[i+1],index_list[i])\n",
    "                    print(k)\n",
    "                    return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
